package com.zhang.study.chapter06;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 合并k个已排序的链表
 * 测试链接地址 <a href="https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6">...</a>
 */
public class Code05_MergeKLists {


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // write code here
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode list : lists) {
            if (list != null) {
                heap.add(list);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }
        ListNode ans = heap.poll();
        ListNode cur = ans;
        if (cur.next != null) {
            heap.add(cur.next);
        }
        while (!heap.isEmpty()) {
            ListNode next = heap.poll();
            cur.next = next;
            cur = next;
            if (next.next != null) {
                heap.add(next.next);
            }
        }
        return ans;
    }


    public static class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }


}
